// test_leetcode.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int num = 0;
        int count_val = 0;
        for (int i = 0; i < 32; i++)
        {
            for (auto n : nums)
            {
                if (n  & (1 << i))    //取第i位，nums的i位加起来如果不是3的倍数，说明单独的那个元素那位就是1，否则是0
                    count_val++;
            }
            if (count_val % 3 != 0)
                num = num | (1 << i);
            count_val = 0;
        }

        return num;
    }
};

class Solution2 {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x = 0; //这是所有数字异或得到的结果
        for (size_t i = 0; i < nums.size(); ++i)
        {
            x ^= nums[i];//排除所有两个以外的元素
        }

        //找到x中为1的位，根据这一位，将nums分为两组
        int bit = 0;
        for (int i = 0; i < 31; i++)
        {
            if (x & (1 << i))
            {
                bit = i;
                break;
            }
        }
        int x1 = 0;
        int x2 = 0;
        for (auto n : nums)
        {
            if (n & (1 << bit))
            {
                x1 ^= n;
            }
            else
            {
                x2 ^= n;
            }
        }

        return { x1,x2 };
    }
};

class Solution2_copy {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sumXOR = 0;
        for(int& n : nums){
            sumXOR ^= n;
        }
        int index = 1;
        while(((sumXOR & index) == 0)){
            index <<= 1;
        }
        int sumXOR1 = 0,sumXOR0 = 0;
        for(int& num : nums){
            if(index & num){
                sumXOR1 ^= num;
            }
            else{
                sumXOR0 ^= num;
            }
        }
        return {sumXOR0,sumXOR1};
    }
};


int main()
{
    vector<int> v;
    v.reserve(4);
    v.push_back(4);
    v.push_back(4);
    v.push_back(4);
    v.push_back(3);
    int n = Solution().singleNumber(v);
   cout << n << endl;
    //int n1 = 1;
    //for (int i = 0; i < 32; i++)
    //{
    //    cout << ((n1 << i)&1) << " ";
    //}
    //cout << endl;


    return 0;
}

